/**
 *  @file alphabet.c
 *  @brief functions for manipulating edge labels of graphs
 *   representing finite automata
 *  @author Matthias Stallmann
 *  @date 1992/02/19
 * $Id: alphabet.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 1992, 2001  Matthias Stallmann.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include <stdio.h>              /* sscanf() */
#include <string.h>             /* strlen() */
#include "Gdr.h"
#include "general.h"
#include "alphabet.h"

#define LAB_SEPARATOR ','  /* separator between consecutive label items */

/* declarations and macros for the animation */
#define MSG_SIZE 1000           /* maximum length of a message */
#define LAB_SIZE 20             /* maximum length of a label */
static char msg[MSG_SIZE];
static TWIN pwin;               /* window for user prompts */
#define XW 1                    /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
				   hide_window(pwin))
#define COUNT 4                 /* number of blinks */

static char alphabet[LAB_SIZE+1];

char *get_alphabet(void) {
  return alphabet;
}

boolean is_in_label(char c, const char *lab)
  /* TRUE if c appears in the label lab */
{
  int retval = FALSE;
#ifdef DEBUG
  if( lab ) {
    fprintf(stderr, "is_in_label( %c, [%s] )\n", c, lab);
  } else {
    fprintf(stderr, "is_in_label( %c, NULL )\n", c );
  }
#endif
  if (!is_letter(c) && !is_digit(c)) {
	sprintf(err_msg,"Warning: %c is not a letter or digit (is_in_label)",c);
	error(err_msg);
  }
  else if (lab != NULL) {
    for ( ; *lab != '\0'; lab++) {
      if (*lab == c) {
        retval = TRUE;
        break;
      }
    }
  } /* lab != NULL */
#ifdef DEBUG
  fprintf(stderr, "is_in_label done: retval = %d\n", retval);
#endif
  return retval;
}

char *label_union(const char *lab1, const char *lab2)
     /* returns an allocated string of the letters and digits of lab1 and
        lab2, separated by LAB_SEPARATOR */
{
  char *new_label;
  int nlp;         /* index of current position in new label */
  char c;          /* generic character */
  boolean first_time;  /* first time through loop -- don't need
						  separator */
#ifdef DEBUG
  if ( lab1 == NULL && lab2 == NULL )
    fprintf(stderr, "label_union(NULL,NULL)\n");
  else if ( lab1 == NULL )
    fprintf(stderr, "label_union(NULL,[%s])\n", lab2);
  else if ( lab2 == NULL )
    fprintf(stderr, "label_union([%s],NULL)\n", lab1);
  else
    fprintf(stderr, "label_union([%s],[%s])\n", lab1, lab2);
#endif

  /* allocate and initialize new label */
  new_label = (char *) malloc(LAB_SIZE + 1);
  nlp = 0;
  first_time = TRUE;

  /* for each letter or digit in lab1 and lab2, add it to new_label,
	 using LAB_SEPARATOR to separate */
  for_in_label(c,lab1) {
    if (!first_time) new_label[nlp++] = LAB_SEPARATOR;
    first_time = FALSE;
    new_label[nlp++] = c;
    if (nlp >= LAB_SIZE) {
      sprintf(err_msg,"Fatal: label overflow %c %d (label_union 1)",c,nlp);
      error(err_msg);
      exit(1);
    }
  } /* for c in lab1 */
  for_in_label(c,lab2) if (!is_in_label(c,lab1)) {
    if (!first_time) new_label[nlp++] = LAB_SEPARATOR;
    first_time = FALSE;
    new_label[nlp++] = c;
    if (nlp >= LAB_SIZE) {
      sprintf(err_msg,"Fatal: label overflow %c %d (label_union 2)",c,nlp);
      error(err_msg);
      exit(1);
    }
  } /* for c in lab2, but not in lab1 */
  new_label[nlp] = '\0';
#ifdef DEBUG
  fprintf(stderr, "label_union done: new_label = [%s]\n", new_label);
#endif
  return (new_label);
}

boolean is_in_alphabet(char c)  /* returns TRUE if c is in the alphabet */
{
  char *cp;  /* pointer to current alphabet char */
  boolean retval = FALSE;

#ifdef DEBUG
  fprintf(stderr, "is_in_alphabet( %c )\n", c );
#endif
  if (!is_letter(c) && !is_digit(c)) {
	sprintf(err_msg,"Warning: %c is not a letter or digit (is_in_alphabet)",c);
	error(err_msg);
  }
  else {
    for (cp = alphabet; (*cp != '\0') && (*cp != c); cp++);
    if (*cp == c) retval = TRUE;
  }
#ifdef DEBUG
  fprintf(stderr, "is_in_alphabet done: %d\n", retval );
#endif
  return retval;
}

void add_to_alphabet(char c)  /* adds c to the alphabet */
	        
{
  char *cp;  /* pointer to current alphabet char */

  if (!is_letter(c) && !is_digit(c)) {
	sprintf(err_msg,
			"Warning: %c is not a letter or digit (add_to_alphabet)",c);
	error(err_msg);
	return;
  }
  if (strlen(alphabet) >= LAB_SIZE - 1) {
	sprintf(err_msg,
			"Warning: alphabet too big, %c not added (add_to_alphabet)", c);
    error(err_msg);
    return;
  }
  for (cp = alphabet; *cp != '\0'; cp++);
  *cp++ = c;
  *cp++ = '\0';
}

void check_dfa(void)  /* makes sure graph represents a valid DFA, i.e. that
                         there is a unique transition defined for every
                         combination of state and alphabet symbol, that there
                         are no extraneous symbols;  a side effect is the
                         initialization of the alphabet (using an arbitrary
                         state as a model) */
{
  vertex v,w;
  edge e;
  char c;
  char *working_label = NULL;   /* used to keep track of list of all
                                   symbols on labels of outgoing edges
                                   of a particular vertex */
  char *old_working_label;      /* saves working label so that allocated
                                   string can be freed */

  init_prompt_window;
  write_text_window(pwin,"Checking DFA...");

 start:
  /* initialize alphabet using an arbitrary vertex -- the symbols
	 appearing in the labels of all its outgoing edges are the alphabet */
  *alphabet = '\0';
  v = get_a_vertex();
  for_adjacent(v,e,w) {
    char * current_edge_label = edge_label(e);
    for_in_label(c,current_edge_label) add_to_alphabet(c);
    free(current_edge_label);
  }

  sprintf(msg,"Alphabet is %s\nClick RESUME to continue",alphabet); 
  wait(msg);

  /* check to make sure outgoing edges of all vertices are consistent
	 with the arbitrary one */
  for_all_vertices(v) {
#ifdef DEBUG
    fprintf(stderr,"Processing vertex %d\n",v);
#endif
    blink_vertex(v,1);
    if (working_label != NULL) free(working_label);
    working_label = NULL;
    /* working_label is the set of symbols encountered on transitions out
       of v so far */
    for_adjacent(v,e,w) {
      char * current_edge_label = edge_label(e);
#ifdef DEBUG
      fprintf(stderr, " Processing edge: (%d,%d) with label [%s]\n",
              tail(e), head(e), current_edge_label);
#endif
      blink_edge(e,1);
      for_in_label(c,current_edge_label) {
        if (!is_in_alphabet(c)) {
          BEEP;
          blink_edge(e,COUNT);
          highlight_edge(e);
          sprintf(msg,
                  "Symbol not in alphabet: %c\nFix problem and click RESUME",
                  c);
          wait(msg);
          un_highlight_edge(e);
          free(current_edge_label);
          goto start;
        } /* c is not in the alphabet */
        if (is_in_label(c,working_label)) {
          BEEP;
          blink_edge(e,COUNT);
          highlight_edge(e);
          sprintf(msg,
            "Multiple transitions on symbol: %c\nFix problem and click RESUME",
                  c);
          wait(msg);
          un_highlight_edge(e);
          free(current_edge_label);
          goto start;
        } /* there's more than one transition on c */
        old_working_label = working_label;
        working_label = label_union(working_label,current_edge_label);
        if (old_working_label != NULL) free(old_working_label);
      } /* for c in label of e */
      free(current_edge_label);
    } /* for edge e incident on vertex v */
    for_in_alphabet(c)
      if (!is_in_label(c,working_label)) {
        BEEP;
        blink_vertex(v,COUNT);
        change_vertex_label(v,working_label);
        expose_vertex_label(v);
        sprintf(msg,"No transition for %c\nFix problem and click RESUME",
                c);
        wait(msg);
        hide_vertex_label(v);
        goto start;
      } /* for c in alphabet, not in working_label */
  }
  destroy_prompt_window;
}

/*  [Last modified: 2007 06 28 at 19:36:00 GMT] */
